package org.example.基于无序数组实现;


import org.example.Priority;
import org.example.Queue;

/**
 * 基于 无 序数组实现优先级队列
 * @param <E>
 */
public class PriorityQueue1<E extends Priority> implements Queue<E> {

    Priority[] array;
    int size;

    public PriorityQueue1(int capacity) {
        array = new Priority[capacity];
    }

    @Override
    public boolean offer(E e) {
        if (isFull()) {
            return false;
        }
        array[size++] = e;
        return true;
    }

    /**
     * 返回优先级最高的索引值
     * @return
     */
    public int selectPriorityIndex() {
        if (isEmpty()) {
            return -1;
        }
        int max = 0;
        for (int i = 0; i < size; i++) {
            if (array[max].priority() < array[i].priority()) {
                max = i;
            }
        }
        return max;
    }

    @Override
    public E poll() {
        if (isEmpty()) {
            return null;
        }
        int i = selectPriorityIndex();
        E e = (E) array[i];
        remove(i);
        return e;
    }

    private void remove(int i) {
        if (i < size - 1) {
            System.arraycopy(array, i + 1, array, i, size - i - 1);
        }
        array[--size] = null;
    }

    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        return (E) array[selectPriorityIndex()];
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean isFull() {
        return size == array.length;
    }
}
